package com.leecode;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 */
public class Leet84 {
	public static void main(String[] args) {
		new Leet84().largestRectangleArea(new int[]{2,1,5,6,2,3});
	}

	/**
	 * 暴力:遍历坚条,尽量左右拓宽,求出max,我不想写
	 */
	public int largestRectangleArea(int[] heights) {
		if(heights==null ||heights.length<1)return 0;

		int[] dp=new int[heights.length];
		dp[0]=heights[0];
		for(int a=1;a<dp.length;a++){
			if(heights[a]>=heights[a-1])dp[a]=Math.max(dp[a-1]+heights[a-1],heights[a]);
			else {
				int width=1;
				int moveB=a-1;
				while(moveB>=0){
					if (heights[moveB]>=heights[a]) {
						width++;
						moveB--;
						continue;
					}
					break;
				}
				dp[a]=heights[a]*width;
			}
		}
		int res=dp[0];
		for(int b=0;b<dp.length;b++){
			if(dp[b]>res)res=dp[b];
		}
		return res;
	}
}
